package com.hp.sort;

public class MergeSort {

    // 合并两个子数组
    private static void merge(int[] array, int left, int middle, int right) {
        int[] leftArray = new int[middle - left + 1];
        int[] rightArray = new int[right - middle];

        // 复制数据到临时数组
        for (int i = 0; i < leftArray.length; i++) {
            leftArray[i] = array[left + i];
        }
        for (int i = 0; i < rightArray.length; i++) {
            rightArray[i] = array[middle + 1 + i];
        }

        // 合并临时数组
        int i = 0, j = 0, k = left;
        while (i < leftArray.length && j < rightArray.length) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // 复制剩余元素
        while (i < leftArray.length) {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        while (j < rightArray.length) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    // 归并排序
    private static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            // 找到中间索引
            int middle = (left + right) / 2;

            // 对左半部分进行排序
            mergeSort(array, left, middle);
            // 对右半部分进行排序
            mergeSort(array, middle + 1, right);

            // 合并两部分
            merge(array, left, middle, right);
        }
    }

    // 主函数，用于测试归并排序
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("原始数组：");
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();

        mergeSort(array, 0, array.length - 1);

        System.out.println("排序后的数组：");
        for (int value : array) {
            System.out.print(value + " ");
        }
    }
}